n=1000;
roads=[|2,1|
3,1|
4,1|
5,1|
1,6|
1,7|
8,1|
1,9|
1,10|
11,1|
1,12|
13,1|
14,1|
1,15|
1,16|
17,1|
18,1|
1,19|
1,20|
21,1|
1,22|
1,23|
1,24|
25,1|
26,18|
1,27|
28,1|
29,1|
1,30|
31,1|
1,32|
1,33|
10,34|
1,35|
1,36|
37,1|
38,14|
39,1|
40,1|
41,1|
1,42|
43,1|
44,1|
1,45|
1,46|
1,47|
1,48|
13,49|
1,50|
51,1|
1,52|
1,53|
1,54|
1,55|
56,1|
57,20|
1,58|
59,1|
1,60|
61,1|
1,62|
63,1|
64,1|
65,1|
1,66|
1,67|
1,68|
69,1|
70,1|
71,1|
1,72|
73,1|
1,74|
75,1|
1,76|
1,77|
78,1|
1,79|
80,1|
81,1|
82,1|
1,83|
84,1|
1,85|
1,86|
1,87|
88,1|
1,89|
90,1|
91,1|
92,1|
93,1|
1,94|
95,1|
1,96|
1,97|
98,1|
69,99|
1,100|
1,101|
102,1|
103,1|
104,11|
105,1|
106,1|
1,107|
108,1|
109,1|
110,1|
111,15|
112,1|
1,113|
114,109|
1,115|
116,90|
117,1|
1,118|
119,1|
120,90|
1,121|
122,1|
123,1|
1,124|
125,1|
1,126|
127,77|
1,128|
129,1|
1,130|
131,1|
132,1|
1,133|
134,1|
1,135|
136,1|
137,1|
1,138|
1,139|
1,140|
141,20|
142,1|
71,143|
144,1|
1,145|
1,146|
147,1|
1,148|
1,149|
1,150|
1,151|
1,152|
58,153|
1,154|
155,1|
1,156|
1,157|
1,158|
159,1|
160,1|
161,1|
46,162|
163,1|
1,164|
165,1|
166,1|
167,1|
1,168|
169,1|
1,170|
1,171|
172,1|
1,173|
1,174|
175,1|
1,176|
1,177|
178,29|
179,1|
1,180|
1,181|
1,182|
1,183|
184,1|
185,1|
1,186|
1,187|
188,1|
189,1|
190,130|
1,191|
1,192|
193,1|
1,194|
1,195|
1,196|
197,1|
1,198|
1,199|
200,1|
1,201|
1,202|
1,203|
204,1|
205,1|
1,206|
1,207|
1,208|
51,209|
210,1|
1,211|
1,212|
1,213|
214,1|
1,215|
216,1|
217,1|
218,1|
207,219|
1,220|
11,221|
222,1|
1,223|
224,1|
225,1|
226,1|
227,1|
1,228|
229,215|
230,1|
231,1|
232,1|
1,233|
234,1|
1,235|
1,236|
237,1|
1,238|
239,1|
1,240|
241,1|
1,242|
243,1|
244,187|
1,245|
1,246|
247,1|
248,1|
1,249|
250,1|
251,1|
252,1|
1,253|
254,1|
1,255|
256,1|
1,257|
258,1|
259,1|
260,1|
261,1|
1,262|
263,1|
1,264|
265,1|
1,266|
1,267|
1,268|
269,1|
1,270|
271,1|
196,272|
1,273|
1,274|
275,1|
1,276|
40,277|
1,278|
1,279|
1,280|
281,1|
282,1|
283,1|
284,1|
285,72|
286,1|
287,282|
288,1|
289,1|
290,187|
148,291|
292,1|
1,293|
294,1|
1,295|
296,1|
1,297|
298,1|
1,299|
300,1|
301,1|
302,1|
1,303|
141,304|
305,1|
1,306|
1,307|
308,224|
1,309|
310,279|
1,311|
1,312|
1,313|
314,1|
315,1|
1,316|
235,317|
318,159|
319,176|
1,320|
159,321|
1,322|
323,317|
1,324|
1,325|
326,1|
327,1|
328,1|
1,329|
1,330|
331,1|
332,1|
1,333|
1,334|
1,335|
336,1|
337,209|
1,338|
1,339|
1,340|
341,1|
1,342|
343,1|
1,344|
1,345|
1,346|
1,347|
348,1|
1,349|
1,350|
265,351|
1,352|
1,353|
1,354|
355,1|
356,1|
1,357|
358,1|
1,359|
360,1|
361,1|
1,362|
363,1|
364,1|
365,1|
366,1|
367,205|
1,368|
1,369|
1,370|
1,371|
1,372|
1,373|
1,374|
1,375|
1,376|
377,1|
378,1|
1,379|
1,380|
1,381|
382,1|
1,383|
1,384|
385,1|
386,1|
387,174|
388,1|
389,1|
1,390|
391,1|
392,247|
393,1|
1,394|
395,1|
396,1|
1,397|
398,1|
1,399|
400,1|
401,1|
1,402|
403,1|
404,1|
405,1|
406,1|
407,1|
408,1|
409,1|
1,410|
411,1|
412,1|
413,1|
1,414|
1,415|
416,1|
417,1|
1,418|
1,419|
1,420|
421,1|
422,1|
1,423|
1,424|
425,236|
1,426|
427,1|
1,428|
429,1|
1,430|
431,1|
1,432|
433,1|
434,1|
435,1|
436,1|
1,437|
1,438|
439,1|
440,1|
1,441|
1,442|
1,443|
444,1|
445,1|
1,446|
447,1|
448,1|
1,449|
1,450|
1,451|
452,66|
453,1|
1,454|
1,455|
456,1|
1,457|
1,458|
459,1|
1,460|
1,461|
462,1|
1,463|
464,1|
1,465|
1,466|
467,1|
468,1|
1,469|
1,470|
1,471|
1,472|
1,473|
474,6|
475,1|
476,270|
477,1|
478,1|
479,1|
480,1|
481,1|
482,1|
483,1|
484,1|
485,1|
486,467|
487,1|
488,354|
489,1|
32,490|
491,1|
492,1|
493,1|
1,494|
495,414|
1,496|
497,1|
498,424|
1,499|
500,1|
1,501|
1,502|
1,503|
504,1|
505,1|
1,506|
1,507|
1,508|
509,1|
510,1|
1,511|
1,512|
1,513|
514,1|
515,1|
1,516|
517,1|
518,1|
519,1|
520,1|
521,1|
522,1|
523,1|
524,1|
1,525|
525,526|
527,525|
525,528|
525,529|
530,525|
531,525|
525,532|
525,533|
20,534|
525,535|
525,536|
525,537|
538,5|
539,525|
525,540|
336,541|
525,542|
543,381|
9,544|
525,545|
546,525|
547,525|
548,435|
525,549|
550,525|
551,525|
552,525|
525,553|
525,554|
525,555|
556,525|
557,525|
525,558|
559,525|
560,525|
561,525|
525,562|
525,563|
564,525|
565,525|
566,525|
525,567|
279,568|
569,525|
570,525|
571,525|
572,525|
525,573|
574,525|
525,575|
78,576|
577,525|
578,525|
525,579|
580,525|
525,581|
582,525|
525,583|
525,584|
525,585|
586,525|
587,225|
525,588|
589,525|
525,590|
591,525|
525,592|
525,593|
594,525|
525,595|
525,596|
597,525|
598,525|
525,599|
525,600|
601,525|
602,525|
603,525|
525,604|
605,525|
525,606|
525,607|
525,608|
525,609|
525,610|
611,525|
612,525|
525,613|
525,614|
615,525|
616,525|
617,525|
618,525|
525,619|
525,620|
525,621|
622,525|
623,525|
624,525|
625,525|
525,626|
627,525|
628,525|
525,629|
630,525|
525,631|
525,632|
633,525|
634,525|
525,635|
636,525|
534,637|
638,525|
639,525|
525,640|
641,525|
525,642|
643,525|
525,644|
275,645|
646,525|
525,647|
648,525|
649,525|
650,525|
651,525|
652,525|
653,364|
525,654|
655,525|
525,656|
525,657|
565,658|
525,659|
660,525|
525,661|
525,662|
663,525|
525,664|
665,525|
666,525|
525,667|
668,525|
525,669|
525,670|
525,671|
672,525|
553,673|
525,674|
525,675|
676,525|
677,525|
678,525|
525,679|
680,525|
681,525|
525,682|
525,683|
525,684|
525,685|
525,686|
687,525|
688,525|
689,266|
525,690|
691,525|
525,692|
525,693|
694,525|
695,38|
696,525|
525,697|
698,545|
699,525|
525,700|
521,701|
702,525|
703,525|
631,704|
705,525|
706,525|
707,525|
708,525|
709,528|
710,525|
170,711|
525,712|
713,525|
714,525|
715,525|
716,525|
717,525|
525,718|
719,525|
525,720|
525,721|
525,722|
723,525|
525,724|
525,725|
726,525|
727,702|
525,728|
525,729|
525,730|
731,525|
525,732|
525,733|
734,525|
525,735|
525,736|
525,737|
525,738|
525,739|
525,740|
741,525|
742,652|
525,743|
744,525|
525,745|
525,746|
525,747|
748,525|
525,749|
525,750|
751,525|
752,525|
525,753|
525,754|
525,755|
525,756|
525,757|
758,525|
759,525|
760,525|
525,761|
525,762|
763,525|
525,764|
765,525|
525,766|
767,525|
525,768|
421,769|
525,770|
525,771|
772,525|
773,525|
774,525|
525,775|
525,776|
777,525|
525,778|
779,525|
780,525|
781,525|
525,782|
525,783|
525,784|
785,525|
786,525|
787,525|
788,525|
525,789|
790,635|
525,791|
525,792|
793,525|
525,794|
491,795|
796,561|
525,797|
798,525|
525,799|
525,800|
801,525|
802,797|
525,803|
804,247|
525,805|
806,525|
525,807|
239,808|
525,809|
810,525|
811,769|
525,812|
813,525|
814,525|
815,525|
525,816|
817,525|
818,525|
819,525|
820,525|
525,821|
525,822|
823,525|
824,525|
525,825|
826,525|
525,827|
525,828|
525,829|
173,830|
525,831|
567,832|
833,525|
525,834|
835,525|
836,525|
525,837|
838,525|
839,525|
525,840|
841,525|
842,525|
525,843|
844,134|
845,525|
846,525|
847,525|
848,525|
849,525|
850,525|
525,851|
852,525|
525,853|
854,525|
855,525|
856,525|
857,707|
858,525|
525,859|
525,860|
525,861|
525,862|
863,525|
525,864|
525,865|
525,866|
867,525|
612,868|
525,869|
870,525|
871,525|
872,742|
525,873|
874,525|
875,513|
876,525|
877,525|
525,878|
879,525|
880,525|
525,881|
525,882|
525,883|
884,525|
885,525|
525,886|
525,887|
525,888|
889,525|
525,890|
525,891|
525,892|
525,893|
894,531|
352,895|
896,525|
897,525|
760,898|
899,525|
900,525|
901,525|
902,525|
525,903|
904,525|
905,525|
525,906|
907,525|
525,908|
909,701|
910,525|
911,525|
525,912|
525,913|
914,525|
525,915|
525,916|
917,391|
918,525|
919,525|
719,920|
921,636|
525,922|
923,525|
924,525|
525,925|
525,926|
525,927|
525,928|
929,525|
930,525|
931,882|
525,932|
933,525|
525,934|
935,525|
936,525|
937,525|
938,525|
525,939|
940,437|
941,525|
748,942|
943,525|
944,525|
525,945|
946,525|
947,525|
948,525|
949,525|
950,525|
525,951|
525,952|
953,525|
525,954|
525,955|
956,525|
525,957|
958,525|
959,525|
525,960|
961,525|
962,525|
963,525|
964,525|
525,965|
966,366|
525,967|
525,968|
525,969|
970,538|
971,525|
972,525|
973,525|
974,525|
525,975|
976,525|
977,525|
525,978|
874,979|
606,980|
981,921|
525,982|
525,983|
525,984|
525,985|
986,525|
987,525|
525,988|
525,989|
525,990|
991,525|
992,525|
525,993|
131,994|
995,525|
996,525|
525,997|
525,998|
525,999|
1000,525|];
W=[43,14,96,25,92,41,65,47,33,89,37,17,53,54,72,67,10,44,46,38,3,32,43,39,33,85,73,29,24,65,58,66,15,31,75,71,78,100,7,12,23,28,44,98,74,29,97,10,10,78,6,15,62,70,44,66,73,63,53,39,33,41,19,91,75,99,42,73,77,11,24,32,49,25,34,53,23,34,33,31,26,84,54,36,88,32,91,11,3,95,33,23,24,37,32,73,52,76,66,29,1,6,96,41,30,63,25,79,91,85,8,97,86,72,40,63,91,11,34,11,5,89,90,12,97,93,54,9,54,82,68,8,88,11,14,100,62,3,65,41,82,98,44,62,74,35,43,31,53,92,57,47,95,43,88,47,80,24,72,82,8,65,92,3,93,54,41,52,93,11,7,65,47,90,63,89,23,93,1,98,39,80,45,20,47,46,35,88,9,20,16,59,97,67,4,60,78,9,15,88,19,55,73,90,82,20,42,41,54,32,39,66,100,50,46,46,27,74,66,96,58,80,70,42,92,80,24,26,81,19,65,75,59,53,8,68,40,39,23,35,52,72,72,88,3,41,36,67,33,91,83,68,70,29,49,45,7,2,35,39,63,31,25,25,69,5,89,67,62,83,65,49,17,64,52,77,21,28,10,58,70,19,45,70,53,88,44,77,17,30,48,55,44,17,79,4,73,81,21,65,65,94,81,26,21,80,3,31,16,79,51,99,35,58,82,45,2,96,39,50,20,66,63,25,33,8,74,96,2,27,29,25,25,83,57,3,10,71,58,83,74,80,74,87,38,83,89,1,37,39,72,16,53,93,16,88,24,84,99,1,59,28,8,78,20,68,88,82,73,88,98,71,14,44,8,46,33,10,65,63,19,38,99,52,66,6,85,41,48,3,1,53,19,64,78,99,84,45,18,66,1,67,98,18,89,4,5,76,83,29,87,35,97,85,93,86,48,94,25,88,89,53,62,24,47,6,31,90,49,7,19,100,34,59,46,88,56,95,5,13,94,99,8,16,89,56,6,54,80,76,68,94,9,86,81,55,84,79,31,8,47,92,38,100,82,90,59,84,93,6,21,54,34,18,35,60,5,73,78,56,31,33,29,77,7,75,73,100,96,48,47,48,81,48,9,50,70,12,68,73,8,8,53,52,31,63,100,88,31,41,97,25,73,47,89,37,91,98,45,10,33,17,81,64,10,69,95,2,33,89,11,53,30,52,86,89,21,66,88,7,80,93,40,4,32,27,38,97,95,95,72,48,46,71,33,39,86,96,7,10,31,36,43,50,22,19,22,80,22,57,6,11,74,9,52,27,29,46,98,88,34,65,74,79,97,92,1,81,50,52,17,72,8,19,42,89,78,95,80,21,31,71,29,64,17,25,43,83,52,81,96,50,57,87,18,39,40,4,22,9,49,28,75,54,98,65,61,27,5,16,54,14,68,100,35,45,27,48,72,33,94,83,91,100,54,15,99,54,24,15,88,54,81,5,57,61,22,92,6,41,92,31,47,25,19,5,13,37,22,14,13,38,50,58,94,67,98,38,28,74,62,2,23,20,67,62,96,66,40,67,93,54,78,65,75,68,84,76,72,35,17,61,30,34,43,90,4,72,46,100,73,77,55,19,92,10,40,57,81,45,93,55,78,91,14,62,42,12,5,73,50,81,70,17,74,60,90,60,6,79,10,2,13,94,63,65,64,30,35,45,44,82,13,92,6,54,24,78,58,24,14,88,95,86,65,47,74,13,49,6,38,97,19,35,38,81,43,46,5,20,25,48,17,67,9,80,8,8,69,27,90,69,93,78,89,43,54,6,93,9,36,20,22,81,69,2,19,32,78,16,76,37,36,49,85,45,89,58,47,39,39,33,58,51,23,44,73,18,2,48,81,13,9,30,40,53,100,47,2,47,64,89,63,20,11,76,97,97,74,88,57,68,39,85,59,28,51,71,61,40,81,46,59,92,16,40,56,2,69,68,66,48,41,71,69,82,59,88,7,28,27,78,9,16,46,64,7,62,15,74,30,37,69,40,4,74,38,3,71,42,22,61,47,47,33,2,45,80,82,58,3,24,61,3,59,11,11,5,85,57,14,18,57,97,78,55,64,7,13,28,56,35,15,82,11,28,5,47,81,28,97,98,10,30,32,26,89,2,68,4,74,53,49,1,1,81,36,89,29,53,29,49,50,52,6,42,21,23,28,5,27,64,10,64,49,19,47,30,85,78,64,88,53,57,37,86,20,36,32,86,49,55,14,18,1,87,81,6,31,14];